package com.cat.dataStructure;

import java.util.ArrayList;
import java.util.List;

/**
 *   @description https://leetcode.cn/problems/insert-interval/
 *   @author 曲大人的喵
 *   @create 2025/8/24 11:17
 *   @since JDK17
 */

public class Solution49 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int max = newInterval[1], min = newInterval[0];
        for (int[] arr : intervals) {
            max = Math.max(arr[1], max);
        }
        int[] diff = new int[max * 2 + 2];
        for (var arr : intervals) {
            diff[arr[0] * 2]++;
            diff[arr[1] * 2 + 1]--;
        }
        diff[newInterval[0] * 2]++;
        diff[newInterval[1] * 2 + 1]--;
        List<int[]> list = new ArrayList<>();
        int last = -1, sum = 0, end = max * 2 + 2;
        for (int i = 0; i < end; i++) {
            sum += diff[i];
            if (sum > 0) {
                if (last == -1) {
                    last = i;
                }
            } else {
                if (last != -1) {
                    list.add(new int[] { last / 2, i / 2 });
                    last = -1;
                }
            }
        }

        return list.toArray(new int[list.size()][2]);
    }
}
